package com.xk._03真题骗._03栈_队列;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/*
 * @description: https://leetcode.cn/problems/daily-temperatures/
 * @author: xu
 * @date: 2022/10/31 0:39
 */
public class _739每日温度 {
    /*
    * 思路：单调递减栈
    * */
    public int[] dailyTemperatures1(int[] temperatures) {
        if (temperatures == null || temperatures.length == 0) return null;
        int len = temperatures.length;
        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                res[idx] = i - idx;
            }
            stack.push(i);
        }
        return res;
    }


    /*
     * 思路：倒推法
     * */
    public int[] dailyTemperatures2(int[] temperatures) {
        if (temperatures == null || temperatures.length == 0) return null;
        int len = temperatures.length;
        int[] values = new int[len];
        for (int i = len - 2; i >= 0; i--) {
            int j = i + 1;
            while (true) {
                if (temperatures[i] < temperatures[j]){
                    values[i] = j - i;
                    break;
                } else if (values[j] == 0) {
                    values[i] = 0;
                    break;
                } else if (temperatures[i] == temperatures[j]){
                    values[i] = values[j] + j - i;
                    break;
                } else {
                    j = j + values[j];
                }
            }
        }
        return values;
    }

    public int[] dailyTemperatures(int[] temperatures) {
        if (temperatures == null || temperatures.length == 0) return null;
        int len = temperatures.length;
        int[] values = new int[len];
        for (int i = len - 2; i >= 0; i--) {
            int j = i + 1;
            while (true) {
                if (temperatures[i] < temperatures[j]){
                    values[i] = j - i;
                    break;
                } else if (values[j] == 0) {
                    values[i] = 0;
                    break;
                }
                j = j + values[j];
            }
        }
        return values;
    }

    public static void main(String[] args) {
        int[] ints = new int[]{75,74,75,75,68,69,69,66};
        int[] temperatures = new _739每日温度().dailyTemperatures(ints);
        System.out.println(Arrays.toString(temperatures));
    }

}
